package com.springboot.demo.sort;

/**
 * 简单选择排序，不稳定
 *
 * <p>
 * 算法思想：
 * <p>
 * 1、首先确定循环次数，并且记住当前数和当前位置
 * <p>
 * 2、将当前位置后面所有的数与当前位置数比较，较小数赋值给 key，并记住较小数的位置
 * <p>
 * 3、比对完成后，将最小的值与第一个数的值交换
 * <p>
 * 4、重复2、3步骤
 *
 * 时间复杂度：o(n^2)
 * 空间复杂度：o(1)
 *
 * @author supu
 * @date 2019-12-12 11:29
 **/
public class SelectSort {
    public static void selectSort(int[] a) {
        int length = a.length;
        // 需要比较的次数，最后一个数不用比较了，故需要 length-1 次比较
        for (int i = 0; i < length; i++) {
            // 当前最小值位置
            int index = i;
            // 当前最小值
            int currentNumber = a[i];
            // 遍历从当前位置之后的比当前值最小的数
            for (int j = i + 1; j < length; j++) {
                if(currentNumber > a[j]){
                    // 比当前值小的数的位置
                   index = j;
                    // 比当前值小的数的值
                   currentNumber = a[j];
                }
            }
            // 当前最小值位置的值赋值为当前值
            a[index] = a[i];
            // 当前最小值赋值给当前位置的值
            a[i] = currentNumber;
        }
    }

    public static void selectSort1(int[] a){
        /*for (int i = 0; i < a.length-1; i++) {
            int min = a[i];
            int index = i;
            for (int j = i+1; j < a.length; j++) {
                if(a[j] < min){
                    min = a[j];
                    index = j;
                }
            }
            a[index] = a[i];
            a[i] = min;
        }*/
        for (int i = 0; i < a.length -1; i++) {
            int index = i;
            int min = a[i];
            for (int j = i+1; j < a.length; j++) {
                if(min > a[j]){
                   index = j;
                   min = a[j];
                }
            }
            a[index] = a[i];
            a[i] = min;
        }
    }
}
